import java.awt.image.BufferedImage;
import java.util.HashMap;
import java.util.Random;
import java.util.concurrent.CyclicBarrier;


public class ParallelSegmentation extends Thread {
	/**
	 * implement the multithreaded segmentation
	 * @param args
	 */

	public static int threshold = 4;
	public static int randomSeed = -1; // -1 = use time as seed
	private int id;
	
	public static long time_start = -1;
	
	public static CyclicBarrier barrier = new CyclicBarrier(SegmentImg.numThreads, new Runnable() {
		public void run()
		{
			System.out.println("Step done in (ms): "+Long.toString((System.currentTimeMillis() - time_start)));
			time_start = System.currentTimeMillis();
		}
	});


	public static int work_remainder;
	public static int work_divisible;

	private static BufferedImage segmentedImage; // output image
	private BufferedImage original;

	private SegmentImg gui;


	private int imagePixels[]; // Array of pixel values from input image, one int for each color/pixel.
	private int labels[];
	private int width;
	private int height;
	private int pixelWidth;

	private int start;
	private int finish;
	/*public static CyclicBarrier barrier_display = new CyclicBarrier(SegmentImg.numThreads, new Runnable() {
		public void run() { 
			System.out.println("Inside the barrier in parallelsegmentation");
			// (Updates the GUI afteSystem.out.println("aa");r each phase. Slow, useful for
			// visual debugging)
			// comment it out for parallel version
			//gui.updateTimer(pp);
			// System.out.println("update timer, thread "+ tid);
			// comment it out for parallel version
			gui.updateSegmentedImage(getSegmentedImage(), false);
			// System.out.println("update segmented image, thread "+
			// tid);
		}
	});;*/

	public BufferedImage getBufferedImage(){
		return segmentedImage;
	}

	public ParallelSegmentation(BufferedImage image, BufferedImage segImage, SegmentImg sa, int labels[], int begin, int end) 
	{

		start = begin;
		finish = end;


		


		// create representation of image; have to split up the image in accordance to the number of threads:
		width = image.getWidth();
		//to account for the number of threads. Each thread gets a strip of the image to analyze. 

		height = image.getHeight();


		//segmentedImage = new BufferedImage(width, height, BufferedImage.TYPE_3BYTE_BGR);
		original = image;
		segmentedImage = segImage;
		
		this.gui = sa;
		this.labels = labels;
		//image.getHeight()

		imagePixels = image.getRaster().getPixels(0, 0, width, height, (int[])null);


		// Space between two pixels in the imagePixel array.
		pixelWidth = original.getSampleModel().getNumDataElements();
	}



	public void setId(int id)
	{
		this.id = id;
	}

	public int[] getLabels()
	{
		return labels;
	}

	private void doSegmentation()
	{

		int pix[] = imagePixels;
		

		int height = finish - start;
		int maxN = Math.max(width, height);

		int phases = (int) Math.ceil(Math.log(maxN) / Math.log(2));

		//System.out.println(tid+": Ok, " + (phases+1) + " phases scheduled...");
		for (int pp = 0; pp <= phases; pp++) {

			// pass one. Find neighbors with better labels.
			for (int i = finish - 1; i >= start; i--) {
				for (int j = width - 1; j >= 0; j--) {
					int idx = i*width + j;
					int idx3 = idx*pixelWidth;

					if (labels[idx] == 0) 
						continue;

					int ll = labels[idx]; // save previous label

					// pixels are stored as 3 ints in "pix" array. we just use the first of them. 
					// Compare with each neighbor
					if (i != finish - 1 && 
							Math.abs(pix[((i+1)*width + j)*pixelWidth] - pix[idx3]) < threshold) 
						labels[idx] = Math.max(labels[idx], labels[(i+1)*width + j]);

					if (i != 0 && 
							Math.abs(pix[((i-1)*width + j)*pixelWidth] - pix[idx3]) < threshold) 
						labels[idx] = Math.max(labels[idx], labels[(i-1)*width + j]);

					if (i != finish - 1 && j != width - 1 && 
							Math.abs(pix[((i+1)*width + j + 1)*pixelWidth] - pix[idx3]) < threshold) 
						labels[idx] = Math.max(labels[idx], labels[(i+1) * width + j + 1]);

					if (i != 0 && j != width - 1 && 
							Math.abs(pix[((i-1) * width + j + 1)*pixelWidth] - pix[idx3]) < threshold) 
						labels[idx] = Math.max(labels[idx], labels[(i-1) * width + j + 1]);

					if (i != finish - 1 && j != 0 && 
							Math.abs(pix[((i+1) * width + j - 1)*pixelWidth] - pix[idx3]) < threshold) 
						labels[idx] = Math.max(labels[idx], labels[(i+1) * width + j - 1]);

					if (i != 0 && j != 0 && 
							Math.abs(pix[((i-1) * width + j - 1)*pixelWidth] - pix[idx3]) < threshold) 
						labels[idx] = Math.max(labels[idx], labels[(i-1) * width + j - 1]);

					if (j != 0 && 
							Math.abs(pix[(i*width + j - 1)*pixelWidth] - pix[idx3]) < threshold)
						labels[idx] = Math.max(labels[idx], labels[i*width + j - 1]);

					if (j != width - 1 && 
							Math.abs(pix[(i*width + j + 1)*pixelWidth] - pix[idx3]) < threshold)
						labels[idx] = Math.max(labels[idx], labels[i*width + j + 1]);

					// if label assigned to this pixel during "follow the pointers" step is worse than label
					// of one of its neighbors, then that means that we're converging to local maximum instead
					// of global one. To correct this, we replace our root pixel's label with better newly found one.
					if (ll < labels[idx]) {
						if (labels[ll - 1] < labels[idx])
							labels[ll - 1] = labels[idx];
					}
				}
			}

			// pass two. propagates the updated label of the parent to the children.
			for (int i = start; i < finish; i++) {
				for (int j = 0; j < width; j++) {
					int idx = i*width + j;
					if (labels[idx] != 0) {
						labels[idx] = Math.max(labels[idx], labels[labels[idx] - 1]); 
						// subtract 1 from pixel's label to convert it to array index
					}
				}
			}

			//System.out.println( "Phase " + (pp) + " done.");

			// (Updates the GUI after each phase. Slow, useful for visual debugging)
			// comment it out for parallel version
			//gui.updateTimer(pp);
			// comment it out for parallel version
			//gui.updateSegmentedImage(getSegmentedImage(), false); 
		}
/*
		for (int pp = 0; pp <= phases; pp++) {
			boolean ischanged = false;
			// pass one. Find neighbors with better labels.
			for (int i = finish - 1; i >= start; i--) {
				for (int j = width - 1; j >= 0; j--) {
					int idx = i*width + j;
					int idx3 = idx*pixelWidth;

					if (labels[idx] == 0) 
						continue;

					int ll = labels[idx]; // save previous label

					// pixels are stored as 3 ints in "pix" array. we just use the first of them. 
					// Compare with each neighbor
					if (i != finish - 1 && Math.abs(pix[((i+1)*width + j)*pixelWidth] - pix[idx3]) < threshold){ 
						labels[idx] = Math.max(labels[idx], labels[(i+1)*width + j]);
						ischanged = true;
					}

					if (i != 0 && Math.abs(pix[((i-1)*width + j)*pixelWidth] - pix[idx3]) < threshold){ 
						labels[idx] = Math.max(labels[idx], labels[(i-1)*width + j]);
						ischanged = true;
					}

					if (i != finish - 1 && j != width - 1 && Math.abs(pix[((i+1)*width + j + 1)*pixelWidth] - pix[idx3]) < threshold){ 
						labels[idx] = Math.max(labels[idx], labels[(i+1) * width + j + 1]);
						ischanged = true;
					}

					if (i != 0 && j != width - 1 && Math.abs(pix[((i-1) * width + j + 1)*pixelWidth] - pix[idx3]) < threshold){ 
						labels[idx] = Math.max(labels[idx], labels[(i-1) * width + j + 1]);
						ischanged = true;
					}

					if (i != finish - 1 && j != 0 && Math.abs(pix[((i+1) * width + j - 1)*pixelWidth] - pix[idx3]) < threshold){ 
						labels[idx] = Math.max(labels[idx], labels[(i+1) * width + j - 1]);
						ischanged = true;
					}

					if (i != 0 && j != 0 && Math.abs(pix[((i-1) * width + j - 1)*pixelWidth] - pix[idx3]) < threshold){ 
						labels[idx] = Math.max(labels[idx], labels[(i-1) * width + j - 1]);
						ischanged = true;
					}

					if (j != 0 && Math.abs(pix[(i*width + j - 1)*pixelWidth] - pix[idx3]) < threshold){
						labels[idx] = Math.max(labels[idx], labels[i*width + j - 1]);
						ischanged = true;
					}

					if (j != width - 1 && Math.abs(pix[(i*width + j + 1)*pixelWidth] - pix[idx3]) < threshold){
						labels[idx] = Math.max(labels[idx], labels[i*width + j + 1]);
						ischanged = true;
					}

					// if label assigned to this pixel during "follow the pointers" step is worse than label
					// of one of its neighbors, then that means that we're converging to local maximum instead
					// of global one. To correct this, we replace our root pixel's label with better newly found one.
					if (ll < labels[idx]) {
						if (labels[ll - 1] < labels[idx]){
							labels[ll - 1] = labels[idx];
							ischanged = true;
						}
					}
				}
			}

			//System.out.println(tid+ ": Doing second pass...");
			// pass two. propagates the updated label of the parent to the children.
			for (int i = start; i < finish; i++) {
				for (int j = 0; j < width; j++) {
					int idx = i*width + j;
					if (labels[idx] != 0) {
						labels[idx] = Math.max(labels[idx], labels[labels[idx] - 1]); 
						
						// subtract 1 from pixel's label to convert it to array index
						ischanged = true;
					}
				}
			}

			//if no changes took place for this phase, then image is done segmenting
			if(ischanged == false){
				System.out.println(id+": early termination");
				break;
			}

			try {
				//System.out.println("update outside the barrier, " + barrier_display.getNumberWaiting() + " waiting");
				//barrier_display.await();
			} catch (Exception e) { }

			// (Updates the GUI after each phase. Slow, useful for
			// visual debugging)
			// comment it out for parallel version
			//gui.updateTimer(pp);
			// System.out.println("update timer, thread "+ tid);
			// comment it out for parallel version
			//gui.updateSegmentedImage(getSegmentedImage(), false);
			// System.out.println("update segmented image, thread "+
			// tid);
			//System.out.println(tid+ ": Phase " + (pp) + " done.");

		}*/
	}
	public void run ()
	{

		System.out.printf(id+": %d to %d\n", start,finish);
		
		
		doSegmentation();

		try {
			getSegmentedImage();
			barrier.await();
		} catch (Exception e) { e.printStackTrace(); }

		
		// cut # of threads in half each time, this is logN..
		for (int thread = 1; thread < Math.log(SegmentImg.numThreads)/Math.log(2)+1; thread++)
		{
			if (id % (Math.pow(2, thread)) == 0)
			{
				
				System.out.println(id+": I will join threads "+id + " and "+( id+1)+" using values " +
						"start:["+(finish-1)+"] and finish:["+finish+"]");
				
				
				int old_start = start;
				int old_finish = finish;
				
				// do segmentation on the border
				start = finish - 1;
				finish = finish + 1;
				doSegmentation();
				
				start = old_start;
				finish = start+(old_finish-start)*2;
			
				System.out.printf(id+": start %d finish %d for size %d\n", start, finish, labels.length);
				
				
				// propogate changes
				for (int i = start; i < finish; i++) {
					for (int j = 0; j < width; j++) {
						int idx = i*width + j;
					
						if (labels[idx] != 0) {
							labels[idx] = Math.max(labels[idx], labels[labels[idx] - 1]); 
							
							// subtract 1 from pixel's label to convert it to array index
							
						}
					}
				}
			} 

			try {
				getSegmentedImage();
				barrier.await();
				System.out.println("Join complete.");
			} catch (Exception e) { e.printStackTrace(); }
		}
		

		try {
			//getSegmentedImage();

			SegmentImg.barrier_finish.await();
		} catch (Exception e) { e.printStackTrace(); }

	}


	public BufferedImage getSegmentedImage() {
		HashMap<Integer,Integer> red = new HashMap<Integer,Integer>();
		HashMap<Integer,Integer> green = new HashMap<Integer,Integer>();
		HashMap<Integer,Integer> blue = new HashMap<Integer,Integer>();

		Random random = new Random();
		// if -R <n> is supplied, use it as seed
		if (randomSeed != -1) {
			random.setSeed(Segmentation.randomSeed);
		}

		random.setSeed(2);

		int array[] = new int[(width * (finish-start)) * 3];


		for (int i = start; i < finish; i++) {
			//System.out.printf(id+" -> %10d: ",i);
			for (int j = 0; j < width; j++) {
				int label = labels[i*width+j];
				if (label == 0) {
					red.put(label, 0);
					green.put(label, 0);
					blue.put(label, 0);
				}

				if (!red.containsKey(label)) {
					red.put(label, (int)(random.nextDouble()*255));
					green.put(label, (int)(random.nextDouble()*255));
					blue.put(label, (int)(random.nextDouble()*255));
				}

				array[((i-start)*width+j)*3+0] = red.get(label);
				array[((i-start)*width+j)*3+1] = green.get(label);
				array[((i-start)*width+j)*3+2] = blue.get(label);
			
				//System.out.printf("%10d", label);
			}
			//System.out.println();
		}
	//	System.out.println(id+": writing to the segmented image bufferedimage with start:["+start+"] and finish:["+finish+"]");

		// Store pixels in BufferedImage
		segmentedImage.getRaster().setPixels(0, start, width, (finish-start), array);

		return segmentedImage;
	}
}
